There are several switching system manufacturers who have designed switching systems for high speed data networks, such as ATM networks, that employ a three-stage Benes network with fixed path routing comprising data links interconnecting each of the switches in adjacent stages. Examples of other well known high speed data packet switching networks include Clos networks and Cantor networks. In order for such a switching system to be non-blocking, the internal data links must be operated at a higher rate than the external links, i.e. the inputs and outputs to the switching system itself. The ratio of a switching system's internal data rate over its internal data links to its external data rate is called a switching system's speed advantage. Minimizing the required speed advantage in order to accommodate expected data traffic is important because the speed advantage contributes directly to the switching system's cost. For example, when a three-stage Benes network switching system is used to carry point-to-point traffic, a speed advantage of three is sufficient to ensure that blocking never occurs. Blocking is a term used to describe an unsuccessful attempt to transmit data over an internal data link, where the existing load on the internal data link when added to the additional load sought to be added would exceed its capacity.
In a switching system with fixed path routing, the route selected for a virtual circuit must take into account the bandwidth in use by other virtual circuits, requiring that a path hunt be performed as in circuit switched networks. Also, as in circuit switched networks, blocking can occur if there is no path through the network with sufficient bandwidth to carry the connection.
In his prior work, the inventor herein has previously shown that a k-stage Benes network comprised switching system can be operated in a non-blocking fashion with a speed advantage of k for point-to-point traffic. See Melon and Turner "Non-Blocking Multi-Rate Distribution Network," Washington University Computer Science Department, WUCS-89-34, the disclosure of which is incorporated herein by reference.
As disclosed herein, the inventor has succeeded in extending his analysis from point-to-point switching systems to switching systems carrying multi-point or multi-cast connections. With prior art methodology, a speed advantage of .sqroot. is required to make an n port network non-blocking for multi-point or multi-cast traffic. However, using the methodology disclosed herein, a five-stage network, comprised of two three-stage Benes networks connected back-to-back, can be operated in a nearly non-blocking fashion with a speed advantage of three. This reduces the cost of non-blocking multi-point switching by a factor of 0.2.sqroot.n. For a 256 port switch, the cost reduction is by a factor of 3.2 and goes up to 6.4 for a 1024 port switch. Also, the same methodology may be extended to incorporate the use of Clos and/or Cantor networks, with the system being structured with a pair of networks connected back-to-back, the first network handling point-to-point traffic only while the second network is permitted to accommodate multi-cast connections. For example, if two three-stage Benes networks are connected back-to-back, the resulting switch fabric is a five-stage switching system (the adjoining stages collapsing into a single stage to reduce the total stages from six to five). Thus, for this particular example, a 3:1 speed advantage will be all that is required for nearly non-blocking operation, with branching permitted only from stage three (the middle stage) on to the fifth stage. For new multi-cast connections, the switching system is strictly non-blocking in that any new multi-cast connection can be added without overloading any internal data link. The algorithm which accommodates the addition of a new multi-cast connection comprises the steps of: 1) identifying the most lightly loaded middle stage switch, labeled Z; 2) establishing connections between each desired multi-cast output and Z; and 3) connecting the input (labeled x) to Z. With this algorithm, a new multi-cast connection comprising the routing of a data packet from an input (x) to a plurality of outputs through the most lightly loaded middle stage switch (Z) may always be added.
A variation of this algorithm may also be used to augment an existing multi-cast connection by adding an output. If the output may not be conveniently added by adding an additional branch from a fourth stage or a third stage switch which already carries the connection, the augmented multi-cast connection may always be reestablished (much as a new connection) using the algorithm just mentioned. Therefore, at most, only one multi-cast connection need be re-routed, the one being augmented. All of the existing multi-cast connections may remain in place. Furthermore, in an ATM environment, the re-routing may be accomplished by changing the multi-cast translation tables in the switches comprising the third and fourth stages only, a process which requires less than one operation per switch. For example, rearranging a multi-cast connection in a 256 port switch requires making changes to at most ten of the multi-cast translation tables.
Generally, the technique for re-arranging an existing multi-point connection to augment it and add at least one additional end point includes the steps of first checking to see if a new branch may be added at any of the stages where branching is permitted. For a five-stage switching system comprised of two, three-stage Benes networks, these would be stages 3-5. Presuming that no additional branch could merely be added, and that re-arranging the existing multi-cast connection is required, the technique includes the steps of first identifying the most lightly loaded third stage switch (Z) and then identifying those fourth stage switches through which the connection passes and which are also connected to Z by links having sufficient capacity to carry the connection. Branches are then added from Z to each of those fourth stage switches. Then, those fifth stage switches having designated outputs for part of the connection which are not connected to the newly branched fourth stage switches are then identified and branches between each of those fifth stage switches and Z are established to complete the connection. With this technique, a multi-cast connection sought to be augmented may first be augmented through adding a branch. If no branch is available having sufficient bandwidth, then this single multi-cast connection is re-routed to accommodate the augmented multi-cast connection with minimal modification to multi-cast translation information in the switches comprising the switching system as other connections are not disturbed.
While the principal advantages and features of the subject invention have been described above, a more thorough understanding may be gained by referring to the drawings and description of the preferred embodiment which follow.